1. Field of the Invention
This invention relates to the field of signal processing and in particular to decompression of statistically encoded digital signals.
2. Background Art Statement
Huffman encoding of numerical data, or more broadly variable bit length encoding of numerical data, is an important part of many data compression algorithms in the field of video processing. Huffman encoding is effective to compress numerical data by taking advantage of the fact that most data sets contain non-uniform probability distributions of data values. When using the Huffman method the data values are encoded using codes of different bit lengths. The more frequently occurring data values are assigned shorter codes and the less frequently occurring data values are assigned longer codes. Thus, the average code length for the data values in the data set is minimized. For typically skewed probability distributions of data values the use of Huffman encoding may achieve a compression factor of between one and one-half and two times.
Many important Compression algorithms do involve Huffman decoding, however, and the decoding of such algorithms on general purpose processors is becoming increasingly widespread. The reason that a fast algorithm for Huffman decoding is required is that conventional algorithms for decoding Huffman data are too slow. The conventional algorithms for decoding a Huffman symbol require traversing a binary tree using successive individual bits from the compressed data bit stream at each node of the tree. When a terminal node of the binary tree is reached, the traversal is complete and the decoded value of the Huffman symbol is determined from a table.
At best, this tree traversal decoding algorithm requires five instructions per bit of the encoded symbol on conventional video processors. In many applications Huffman symbols tend to average about four bits each. Thus, approximately twenty instructions or about eighty cycles per symbol are required on a conventional video processor. At approximately three hundred thousand symbols per second, a typical symbol rate for thirty frame per second video displays, this results in twenty-four megahertz. A bit-by-bit method such as this thus requires most of the available cycles on a conventional twenty-five megahertz video processor. Even on a more powerful video processor, a large fraction of the available cycles are required to execute this type of bit-by-bit algorithm. This is not acceptable because Huffman decoding is typically only a small part of the total amount of work required in a video processing system.
In order to perform Huffman processing quickly, it would be advantageous to avoid processing one bit of the bit stream at a time and decode each Huffman symbol as a whole.
It is also desirable in performing Huffman processing to avoid the requirement of accessing the bit stream on non-byte boundaries because this type of accessing involves expensive bit manipulation. However, it is difficult to avoid accessing on non-byte boundaries because the Huffman codes in the bit stream are packed together without regard to byte boundaries.